10869. Строительная конструкция

Заданы n зданий с высотами h₁, h₂, …, h_n. Ваша цель — сделать все здания одной высоты. Это можно сделать, удалив кирпичи из здания или добавив в него несколько кирпичей. Удаление или добавление кирпича производится за определенную плату, которая будет указана вместе с высотой зданий. Найдите минимальную стоимость, за которую можно сделать здания красивыми, реконструировав здания так, чтобы n зданий удовлетворяли условию h₁ = h₂ = ... = h_n = k (k может быть любым целым неотрицательным числом).

Для удобства все постройки представляют собой вертикальные сваи из кирпича, которые имеют одинаковые размеры.

Вход. Первая строка содержит количество зданий n (n ≤ 10⁵). Вторая строка содержит n целых чисел – высоты зданий h₁, h₂, …, h_n (0 ≤ h_i ≤ 10⁴). Третья строка содержит n целых чисел c₁, c₂, ..., c_n (0 ≤ c_i ≤ 10⁴) – стоимость добавления или удаления кирпича из соответствующего здания.

Выход. Выведите минимальную стоимость, за которую можно сделать все постройки красивыми.

Пример входа 1	Пример выхода 1
4 2 3 1 4 10 20 30 40	110
Пример входа 2	Пример выхода 2
3 1 2 3 10 100 1000	120

РЕШЕНИЕ

тернарный поиск

Анализ алгоритма

Отсортируем здания по высоте так, чтобы h₁ ≤ h₂ ≤ …≤ h_n. Здания с одинаковыми высотами сортируем по возрастанию стоимости добавления / удаления.

Найдем стоимость, за которую можно высоту всех домов сделать равной h_x (1 ≤ x ≤ n). Она равна

Функция f(x) вогнутая и имеет глобальный минимум, который ищется тернарным поиском.

Пример

Рассмотрим первый пример. Отсортируем здания по высотам:

Найдем значение функции f(x) для всех значений высот:

· f(1) = (1 – 1) * 30 + (2 – 1) * 10 + (3 – 1) * 20 + (4 – 1) * 40 = 170,

· f(2) = (2 – 1) * 30 + (2 – 2) * 10 + (3 – 2) * 20 + (4 – 2) * 40 = 130,

· f(3) = (3 – 1) * 30 + (3 – 2) * 10 + (3 – 3) * 20 + (4 – 3) * 40 = 110,

· f(4) = (4 – 1) * 30 + (4 – 2) * 10 + (4 – 3) * 20 + (4 – 4) * 40 = 130

Минимум функции f(x) достигается при x = 3, при этом f(3) = 110.

Реализация алгоритма

Каждое здание имеет высоту h и стоимость cost добавления / удаления этажа. Информацию о зданиях храним в массиве b.

#define MAX 100001

struct Building

{

int h, cost;

};

Building b[MAX];

Функция cmp является компаратором для сортировки зданий. Здания сортируем по увеличению высоты. Если высоты зданий одинаковы, то сортируем по увеличению стоимости.

int cmp(Building a, Building b)

{

if (a.h == b.h)

return a.cost < b.cost;

return a.h < b.h;

}

Функция f вычисляет стоимость, за которую можно сделать все постройки равными высоте здания номер x.

long long f(int x)

{

long long ret = 0;

for (int i = 1; i <= n; i++)

ret += 1LL * abs(b[x].h - b[i].h) * b[i].cost;

return ret;

}

Функция ternary_search при помощи тернарного поиска ищет такое x ∈ [left; right], что f(x) минимально. Изначально [left; right] = [1; n].

long long ternarySearch(int left, int right)

{

while (right - left >= 3)

{

int a = left + (right - left) / 3;

int b = left + 2 * (right - left) / 3;

if (f(a) > f(b))

left = a;

else

right = b;

}

Разница между left и right не больше 3. Ищем минимум f(x) на промежутке [left; right] полным перебором.

long long res = f(left++);

while (left <= right)

res = min(res, f(left++));

return res;

}

Основная часть программы. Читаем входные данные.

scanf("%d", &n);

for (i = 1; i <= n; i++)

scanf("%d", &b[i].h);

for (i = 1; i <= n; i++)

scanf("%d", &b[i].cost);

Сортируем здания.

sort(b + 1, b + n + 1, cmp);

Вычисляем и выводим ответ. Здания нумеруются от 1 до n.

printf("%lld\n", ternarySearch(1, n));